package backtrack;
import java.util.*;
public class _02_216_组合总和Ⅲ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
    	backtracking(k, n, 1);
    	return result;
    }
    
    public void backtracking(int k , int n, int startIndex ) {
    	
    	if(item.size() == k) {
    		if(sum == n) {
        		result.add(new ArrayList(item));
    		}
    		return;
    	}

    	
    	for(int i = startIndex; i <= 9 - (k-item.size()) + 1; i++) {
    		item.add(i);
    		sum += i;
    		backtracking(k, n, i + 1);
    		sum -= item.get(item.size() - 1);
    		item.remove(item.size() - 1);
    	}
    	
    }
	public static void main(String[] args) {
		_02_216_组合总和Ⅲ a = new _02_216_组合总和Ⅲ();
		a.combinationSum3(3,9);
//		System.out.println();
	}
}
